#ifndef T_TREE_H
#define T_TREE_H

#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include "cube.h"
#include "common.h"

struct Node
{
	// -1 indicates null
    int parent, left_child, middle_child, right_child, cube_id;
	Node() : parent(-1), left_child(-1), right_child(-1), middle_child(-1), cube_id(-1) {}
	int& operator[](int index)
	{
        return (&parent)[index];
	}
};
class TTree
{
	friend class SA_Solver;
public:
    TTree(std::vector<Cube> &_cubes);
	// Total nodes.
	int GetN()
	{
		return n_;
	}
	int GetVolume()
	{
		return volume_;
	}
	void GetPlacement(std::vector<Cube> &res)
	{
		res = cubes_;
	}
	// Swap node u and node v.
	void SwapNode(int u, int v);
	// Move node u to node v.
	void MoveNode(int u, int v);
	// Modify cube u (i.e. node u) through the kth transition.
	void ModifyCube(int u, int k);
private:
	void PrintTree();
	bool CheckValid();
	// Convert node_index to cube.
	Cube& cube(int index)
	{
		assert(index >= 0 && index < n_);
		return cubes_[nodes_[index].cube_id];
	}
	
	// Convert the T-tree to a cube placement. volume_ and cubes_ will be updated.
	void TreePacking();
	// Randomlly generate a T-tree.
	void Generate();
	// Decompose the tree and determine each cube's coordinates in the u-root tree into which the orinal tree is decomposed.
	void TreeDecomposition(int u);
	//void BinaryTreePacking(int u);
	void PlaceModule(int u);
	// scan the list to find the maximum y coordinate of points that intersect with cube(u) in the Z axis.
	void FindMaxY(int u);
	// scan the determined_cubes_ vector to find the maximum x coordinate of cubes that intersect with cube(u) in the Y-Z plane.
	void FindMaxX(int u);
	void InsertX(int u);
	void ComputeVolume();
	static int count_;
	int volume_, n_, root_, change_node_1_, change_node_2_;
	std::vector<Node> nodes_;
	std::vector<Cube> cubes_;
	static std::vector<int> determined_cubes_;
	static std::vector<int> cur_binary_tree_cubes_;
	static Stack<int> S, S1;
	//Stack<int> S, S1;
	// std::list<ListNode> contour;
	// std::list<ListNode>::iterator cur;
	static List<ListNode> contour;
	LIterator<ListNode> cur;
	// static std::vector<LIterator<Cube> > start_z, end_z;
	// static List<Cube> cube_list_;
	static std::vector<LIterator<Cube> > start_z, end_z;
	static List<Cube> cube_list_;
	LIterator<Cube> cube_list_head_;
	bool visited_change_nodes, computed_before_;
};


#endif /* T_TREE_H */
